1. Field of the Invention
The present invention relates to the field of computer generated graphics, in particular, to systems which utilize texture mapping.
2. Prior Art
In computer graphics systems, a known technique for generating pixel shading values is texture mapping. Basically, texture mapping involves mapping predetermined pixel shading values (the texture map) to a surface being rendered. The texture map is typically stored in a random access storage means (e.g. a Dynamic Random Access Memory or DRAM) that is accused by the graphical system during the rendering of a graphical image. This arrangement allows for utilizing different texture maps.
Entries in a texture map are accessed by a (u,v) coordinate system. Pixels on a screen are addressed by (x,y) coordinates. Pixels are associated with entries in the texture map by a functional mapping of the pixels (x,y) coordinates to the (u,v) coordinates of the texture map. Generally, there will be a one to one relationship between the pixels on the display and the entries on the texture maps.
A complication with the use of texture maps is encountered when a graphical system provides for the zooming of images. A zoom operation requires a filtering operation be performed on the values from the texture map in order to obtain an acceptable image. Here, filtering involves the averaging of corresponding pixel values. For example, if the graphical image is to be reduced in size by 4, one pixel in the display would now correspond to 4 pixels in the texture map. The value for the one pixel would be the average of the 4 corresponding pixels. Performing such averaging "on the fly" can be detrimental to rendering speed.
One approach to this problem is to store the texture map as a MIP (Multum In Pravo- many things in a small place) map. MIP maps are described in a paper entitled "Pyramidal Parametrics", by Lance Williams, Computer Graphics, Vol. 17, Number 3, July 1983. In a MIP map, the texture is stored as a series of recursively filtered images, each image being one-quarter of the previous image. Each of the various resolution images are referred to as "pages" of the MIP map. Such a MIP map is illustrated in FIG. 1. A 32.times.32 image 101 provides the highest resolution in this example. Four texture values (u.sub.1, v.sub.1) 107, (u.sub.2, v.sub.2) 108, (u.sub.3, v.sub.3,) 109 and (u.sub.4, v.sub.4) 110 are in the 32.times.32 image 101. The values 107-109 are averaged to create a value (u.sub.1 ', u.sub.2 ') 111 of 16.times.16 image 102. This occurs for all the texture values in the 32.times.32 image 101 into the corresponding 16.times.16 image 102. Similarly, each texture value in 8.times.8 image 103 is created from four texture values in 16.times.16 image 102. This repeats for the 4.times.4 image 104, 2.times.2 image 105 and 1.times.1 image 106. It should be noted that the use of MIP maps may not eliminate the need for pixel averaging, but will cause a reduction in the number of averaging operations performed.
The pixels for a given map page are stored contiguously, so the address of pixel (x,y) is M+x* RowSize+y, where M is the offset for the map page, and RowSize is the number of pixels per line in the map page. For a 256.times.256 MIP map, M follows the sequence 0, 256.sup.2, 256.sup.2 +128.sup.2, . . . , 256.sup.2 +128.sup.2 +64.sup.2 +32.sup.2 +16.sup.2 +8.sup.2 +4.sup.2 +2.sup.2. Frequently, more than one texture map will be utilized to create the desired graphical image. In this case a more generalized version of the address equation becomes pixel (x,y) is T+M+x*RowSize+y, where T is the base address of the MIP map being used. Table 1 shows the resulting memory map when two 256.times.256 MIP maps are stored contiguously. In Table 1, each MIP map is stored in a contiguous region of memory starting at address T(MapID)=MapID.87381.
TABLE 1 ______________________________________ Memory map for two 256.times.256 MIP maps T M RowSize Data ______________________________________ 0 +0 256 Map 0, page 0 (256.times.256) 0 +65536 128 Map 0, page 1 (128.times.128) 0 +81920 64 Map 0, page 2 (64.times.64) 0 +86016 32 Map 0, page 3 (32.times.32) 0 +87040 16 Map 0, page 4 (16.times.16) 0 +87296 8 Map 0, page 5 (8.times.8) 0 +87360 4 Map 0, page 6 (4.times.4) 0 +87376 2 Map 0, page 7 (2.times.2) 0 +87380 1 Map 0, page 8 (1.times.1) 87381 +0 256 Map 1, page 0 (256.times.256) 87381 +65536 128 Map 1, page 1 (128.times.128) 87381 +81920 64 Map 1, page 2 (64.times.64) 87381 +86016 32 Map 1, page 3 (32.times.32) 87381 +87040 16 Map 1, page 4 (16.times.16) 87381 +87296 8 Map 1, page 5 (8.times.8) 87381 +87360 4 Map 1, page 6 (4.times.4) 87381 +87376 2 Map 1, page 7 (2.times.2) 87381 +87380 1 Map 1, page 8 (1.times.1) ______________________________________
During the actual rendering process, the MIP mapping algorithm requires four pixels from each of two adjacent map pages to compute a filtered texture value. In general, a single MIP mapping filter operation requires fetching pixels (n, m) (n, re+1), (n+1,m), and (n+1, m+1) from page p, and pixels (n/2, m/2) (n/2, m/2+1), (n/2+1,m/2), and (n/2+1, m/2+1) from page p+1. Thus, it is desirable to generate pixel addresses and be able to access pixels from the texture map as quickly as possible.
One technique for increasing the rate of retrieving pixel values is to retrieve multiple pixels simultaneously. To retrieve multiple pixels simultaneously from the RAM, it is necessary to partition the data between multiple memory banks such that different pixels are stored in different banks. FIG. 2 shows an example where the RAM is split into two banks, each with 262144/2=131072 pixels. Referring to FIG. 2, bank A 207 stores even pixel addresses and bank B 208 stores odd pixel addresses. With this memory arrangement it is possible to fetch two MIP map pixels simultaneously; for example, the 8 fetches required for performing a filter operation can be grouped into four even/odd address pairs in the pattern {(n,m),(n,m+1)}, {(n+1,m),(n+1,m+1)}, {(n/2,m/2), (n/2,m/2+1)}, {(n/2+1,m/2), (n/2+1,m/2+1)}. This technique allows the 8 pixels to be fetched in four operations, each operation fetching an adjacent pair of pixels with even and odd addresses.
Referring back to FIG. 2, each pixel address, namely pixel (x,y) 201 and pixel (x, y+1) 202 are provided to an address swapping means 203. The address swapping means insures that a pixel address is directed towards the appropriate memory bank. For both addresses, the constant is discarded by a means for discarding low order constant bit, 204 and 205 respectively. Note that the dashed line 206 refers to a physical interface between a rendering component and the texture map storage. For example, the physical interface would be pins on a rendering component and address pins of the DRAMs or SRAMs of the texture map storage. Note that in this case, 34 address signal pins are needed on the rendering component.
The addresses are then provided to the respective memory banks, 207 and 208. The retrieved data is then provided to a data swapping means 209. The data swapping means swaps the data output signals if there was a prior address swap. This insures that the proper data is assigned to the proper pixel address. Finally, the proper pixel (x,y) data 210 and pixel (x, y+1) data 211 is provided. Note that this latter data swapping means may be embodied within the rendering component.
A drawback of this technique is that it requires two complete sets of address signals be generated and implemented. As a rendering component is typically separate from the texture map storage, the rendering components must include an increased number of address lines to connect to the texture map storage. A rendering component may typically be an integrated circuit. Because generating additional address signals raises the cost of the integrated circuit by increasing the number of address pins needed, it would be desirable to use an addressing scheme where the multiple memory banks share address signals.